%
%  pyPhon
%
%----------------------------------------------------------------------------%
%                    Basic page layout parameters                            %
%----------------------------------------------------------------------------%

\documentclass[12pt]{article}
\usepackage[letterpaper,hmargin=25mm,vmargin=25mm]{geometry} 

\usepackage[bottom]{footmisc}


\usepackage{fancyhdr}
\lhead{}
\chead{}
\rhead{}
\lfoot{}
\cfoot{word count: 472}
\rfoot{}
\pagestyle{fancy}
\renewcommand{\headrulewidth}{0pt} 

\usepackage{setspace}
\singlespacing

\usepackage{enumitem}
\setlist{noitemsep} 

\usepackage{booktabs}

%----------------------------------------------------------------------------%
%                    Title, author, and affiliation                          %
%----------------------------------------------------------------------------%

\title{\textbf{pyPhon}}
\author{Max Bane and Jason Riggle \\ University of Chicago}
%\author{ ~ \\ ~ }
\date{\today}

%----------------------------------------------------------------------------%
%                    Fonts and encoding                                      %
%----------------------------------------------------------------------------%

\usepackage[dirty,tipa]{ucs}	% Utf-8
\usepackage[utf8x]{inputenc}	% fonts
\usepackage[T1]{fontenc}		% in Tex

\usepackage{tipa}
\usepackage{pifont}


%----------------------------------------------------------------------------%
%                    Graphics and figures                                    %
%----------------------------------------------------------------------------%

\usepackage{wrapfig}
\usepackage{graphicx}
\usepackage{multido}
\usepackage{pstricks}

\psset{gridcolor=green, subgridcolor=white, dimen=middle,
	   linewidth=1pt, subgriddiv=1, gridlabels=4pt, gridwidth=0.2pt}
		
\newpsstyle{final}{linewidth=0.5pt,fillstyle=solid,fillcolor=gray95,%
				   doubleline=true,doublesep=0.8pt,dimen=outer}


%----------------------------------------------------------------------------%
%                    Algorithms and Theorems                                 %
%----------------------------------------------------------------------------%

\usepackage[ruled,noend,linesnumbered]{algorithm2e}

\usepackage[leqno,fleqn]{amsmath}
\usepackage{amsthm}
\usepackage{amssymb} 
\usepackage{stmaryrd}

\newtheoremstyle{dotless}{}{}{\normalfont}{}{\bfseries}{}{ }{}
\theoremstyle{dotless}
\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}

\newtheoremstyle{dotlessdefn}{}{}{\normalfont}{}{\bfseries}{}{ }{}
\theoremstyle{dotlessdefn}
\newtheorem{defn}[thm]{Definition}

%\newtheoremstyle{dotlessremark}{}{}{}{}{\itshape}{}{ }{}
%\theoremstyle{dotlessremark}
%\newtheorem{ex}[thm]{Example}

%----------------------------------------------------------------------------%
%                    Bibliography                                            %
%----------------------------------------------------------------------------%

\usepackage{natbib} 
\bibpunct[:]{(}{)}{,}{a}{}{,}

%----------------------------------------------------------------------------%
%                    Hyperlinks                                              %
%----------------------------------------------------------------------------%

\usepackage{hyperref}			% Clickable links in pdfs
\hypersetup{colorlinks,			% nice for large docs and 
			breaklinks,			% for links to web pages
            linkcolor=black,
			urlcolor=darkblue,
            anchorcolor=darkblue,
			citecolor=black}

			%----------------------------------------------------------------------------%
%                    Other packages                                          %
%----------------------------------------------------------------------------%

\usepackage{covington}
\usepackage{calc}
\usepackage{ifthen}
			%----------------------------------------------------------------------------%
%                    New Commands                                            %
%----------------------------------------------------------------------------%

\newcommand{\hand}{{\large \ding{43}}}		% OT-Hand
\newcommand{\Con}[1]{{\sc #1}}				% Constraint-name typeface
\newcommand{\M}[1]{$\llbracket${\sc #1}%	% 'FSA-name' typeface
				   $\rrbracket$}

\newcommand{\Adm}[1]{\text{\raisebox{2pt}{$\,\underrightarrow{#1}\,$}}}

%\newcommand{\Or}{\begin{pspicture}(0.25,0)
%		\rput(0.1,0.1){\scalebox{0.58}{$\mathcal{R}$}}
%		\pscircle[linewidth=0.2pt](0.1,0.1){0.125}\end{pspicture}}

\newcommand{\Or}{\ensuremath{\min_\mathcal{R}}}
\newcommand{\Ur}{\ensuremath{\sqcup_\mathcal{R}}}
\newcommand{\Ptr}{\ensuremath{\times_\mathcal{R}}}

\newcommand{\stack}[2]{\genfrac{}{}{0pt}{}{#1}{#2}}
\newcommand{\NIL}{\ensuremath \varnothing}
\newcommand{\NILc}{$\NIL,\{\epsilon\}$}
\newcommand{\INF}{{\scriptsize $\infty$}}
\newcommand{\INFc}{{\scriptsize $\infty$}\hspace{0.5pt},$\;\emptyset$}
\newcommand{\odv}{\begin{pspicture}(0,0)
\rput(-.05,0.19){{\footnotesize $ons,$}}
\rput(0.05,-.18){{\footnotesize $dpv$}}
\end{pspicture}}
\newcommand{\dvc}{\begin{pspicture}(0,0)
\rput(0,0.2){{$dpv,$}}
\rput(0.1,-.2){{$dpc$}}
\end{pspicture}}
\newcommand{\minn}{{\textbf{min}}}
\newcommand{\hopt}{$\mathcal{H}$\Con{-Opt}}
\newcommand{\minr}[2]{\textbf{min}$_{\mathcal{R}}$(#1,#2)}
\newcommand{\Hr}{$\succ_{\mathcal{R}}$}
\newcommand{\con}{{\sc Con}}
\newcommand{\cinf}{$\infty$}
\newcommand{\rd}[1]{\textcolor{red}{\textbf{#1}}}
\newcommand{\bl}[1]{\textcolor{blue}{\textbf{#1}}}
\newcommand{\pur}[1]{\textcolor{purp}{\textbf{#1}}}
\newcommand{\eval}{E{\footnotesize{VAL}}}
\newcommand{\heval}{$\mathcal{H}$-E{\footnotesize{VAL}}}
%\newcommand{\evala}{$\llbracket$E{\footnotesize{VAL}}$_\mathcal{A}\rrbracket$}
\newcommand{\evala}{$\llbracket$E{\footnotesize{VAL}}$\rrbracket$}
\newcommand{\gen}{\ensuremath{Gen}}
\newcommand{\io}{$(input,output)$ }
\newcommand{\D}{{\Large\bf{.}}}
\newcommand{\DOT}{{\Large\bf{.}}}
\newcommand{\depc}{{\sc{DepC}}}
\newcommand{\depv}{{\sc{DepV}}}
\newcommand{\Max}{{\sc{Max}}}
\newcommand{\ons}{{\sc{Onset}}}
\newcommand{\noc}{{\sc{NoCoda}}}
\newcommand{\cln}{\hspace{1pt}:\hspace{1pt}}
\newcommand{\aaa}{$\alpha$$\to$$\alpha$\cln\oset}
\newcommand{\maxa}{\Con{x}$\to$$\varnothing$\cln\{$max$\}}
\newcommand{\depa}{$\varnothing$$\to$\Con{x}\cln\{$dep$\}}
\newcommand{\dep}[1]{$\varnothing$$\to$\Con{#1}\cln%
										 \{$dep$\hspace{0.33pt}-\Con{#1}\}}

%----------------------------------------------------------------------------%
%                    New colors                                              %
%----------------------------------------------------------------------------%

\newrgbcolor{purp}{0.7 0.0 0.7}
\newrgbcolor{ltblue}{0.8 0.9 1.0}
\newrgbcolor{ltgreen}{0.8 1.0 0.85}
\newrgbcolor{ltred}{1.0 0.9 0.8}
\newrgbcolor{red}{0.7 0.0 0.0}
\newrgbcolor{blue}{0.0 0.0 0.7}
\newrgbcolor{darkblue}{0.0 0.0 0.4}
\newrgbcolor{ltelo}{1.0 1.0 0.8}
\newrgbcolor{ltpurple}{1 0.8 1}

\newgray{gray4}{0.4}
\newgray{gray6}{0.6}
\newgray{gray8}{0.8}
\newgray{gray9}{0.9}
\newgray{gray90}{0.9}
\newgray{gray95}{0.95}
\newgray{gray97}{0.97}

%----------------------------------------------------------------------------%
%                    A tableau environment                                   %
%  [#1-1st Col %-width]  #2-n.Constraints   #3-n.Candidates   #4-Col wid/cm  %
%----------------------------------------------------------------------------%
\newcounter{xc}	  \newcounter{x0}
\newcounter{yc}	  \newcounter{y0}	  
\newcounter{zc}   \newcounter{z0}		\newlength{\rowmax} 
\newlength{\col}  \setlength{\col}{1mm}
\newlength{\row}  \setlength{\row}{1.1mm}
\newboolean{ding} \setboolean{ding}{false}

\newenvironment{tableau}[4][2]{%
\bigskip\medskip\refstepcounter{equation}%
\setcounter{xc}{#2-1}   		\setcounter{x0}{#2}
\setcounter{yc}{#3+1}  			\setcounter{y0}{#3}
\setcounter{zc}{10*\real{#1}-5} \setcounter{z0}{10*\real{#1}-5}
\setcounter{enumi}{1}
\psset{xunit=#4mm,yunit=1.55pt,linewidth=0.6pt,framearc=0}
% \noindent\begin{pspicture}(0,0)\rput[l](0,#35){(\theequation)}\end{pspicture}%
% \hspace*{8.75mm} %<--Tableau inset
\hspace*{0.1mm} %<--Tableau inset
\begin{pspicture}(-\arabic{z0},5)(\arabic{x0}5,\arabic{yc}5)%\psgrid
\multido{\ir=#30+-10}{#3}{\rput[l](-\arabic{z0},\ir)%
		{\hspace{2pt}\textit{\alph{enumi}}.\stepcounter{enumi}}}
\setcounter{xc}{#2+1} \setcounter{yc}{#30+10}
\setlength{\rowmax}{\arabic{xc}mm} \setcounter{xc}{0}
\psdot[linecolor=ltblue](0,30)}{ %Begin Code -|- End Code
\setcounter{yc}{\value{y0}+1}
\multido{\nh=05+10}{\arabic{x0}}{\psline[linestyle=dashed,dash=2pt 1pt,%
		linewidth=0.5pt,dimen=middle](\nh,5)(\nh,\arabic{yc}5)}
\multido{\nw=15+10}{\arabic{y0}}{\psline(-\arabic{z0},\nw)(\arabic{x0}5,\nw)}
\psline[linewidth=1.4pt](5,5)(5,\arabic{yc}5)
\psline[linewidth=1.4pt](-\arabic{z0},\arabic{y0}5)(\arabic{x0}5,\arabic{y0}5)
\psline[linecolor=white](5,5)(5,\arabic{yc}5)
\psline[linecolor=white](-\arabic{z0},\arabic{y0}5)(\arabic{x0}5,\arabic{y0}5)
\psframe[linewidth=1pt,framearc=0.025,dimen=middle]%
(-\arabic{z0},5)(\arabic{x0}5,\arabic{yc}5)
\end{pspicture}\par\medskip}

\newcounter{n1}	\newcounter{n2}
\newcommand{\Shade}[5][gray90]{%
			\setcounter{n1}{#2*10-5}\setcounter{n2}{#3*10-5}
			\psframe*[linecolor=#1](\arabic{n1},\arabic{n2})(#45,#55)}

\newcommand{\Wins}[1]{\setcounter{n1}{\value{y0}-#1+1}%
			\setboolean{ding}{true}%
			\rput[l](-\arabic{z0},\arabic{n1}0){~~~\hand}}
			
\newcommand{\Solid}[1]{\setcounter{n1}{\value{y0}+1}
			\psline[linewidth=0.8pt,dimen=middle](#15,5)(#15,\arabic{n1}5)}

\newcommand{\C}[1]{\ifthenelse{\lengthtest{\row=1.1mm}}{%
		   	\rput[l](-\arabic{z0},\arabic{yc}){%
			\ifthenelse{\lengthtest{\col>\row}}{\hspace{5mm}%
			\ifthenelse{\boolean{ding}}{\phantom{\hand}}{}#1}%
			{\hspace*{3mm}#1}}
		   	\addtocounter{xc}{10}\addtolength{\row}{1mm}}{%
		   	\rput(\arabic{xc},\arabic{yc}){%
			\ifthenelse{\lengthtest{\col>\row}}{#1}{\Con{#1}}}
		   	\ifthenelse{\lengthtest{\row<\rowmax}}%
		   	{\addtocounter{xc}{10}\addtolength{\row}{1mm}}%
		   	{\setcounter{xc}{0}\addtocounter{yc}{-10}
		    \addtolength{\col}{10cm}\setlength{\row}{1.1mm}}}}


%----------------------------------------------------------------------------%
%%%%%%%%%-%%%%%%%%%-%%%%%%%%%-%%%%%%%%%-%%%%%%%%%-%%%%%%%%%-%%%%%%%%%-%%%%%%%%
%./\..../\..../\..../\..../\..../\..../\..../\..../\..../\..../\..../\..../\.%
%/  \../  \../  \../  \../  \../  \../  \../  \../  \../  \../  \../  \../  \%
%    \/    \/    \/    \/    \/    \/    \/    \/    \/    \/    \/    \/    %
%%%%%%%% %%%%%%%% %%%%%%%% %%%%%%%% %%%%%%%% %%%%%%%% %%%%%%%% %%%%%%%% %%%%%%
%----------------------------------------------------------------------------%
\begin{document}
%----------------------------------------------------------------------------%
% \thispagestyle{empty} 
\spacing{1.2}
\noindent
\rput[Bl](0.03,0.9){\textbf{\large Learning From Ambiguous Data}}
% \psline[linewidth=1.5pt,linecolor=gray4](0,1.35)(0.41\textwidth,1.35)
% \psline[linewidth=1.5pt,linecolor=gray4](0,0.67)(0.41\textwidth,0.67)
%
\noindent The pervasiveness of ambiguity in natural language presents a significant learning challenge: upon observing ambiguous forms, what inferences 
\rput(-0.68,-2.13){\psframe*[linecolor=ltblue](0,0)(8,1.12)}
can a learner draw about the grammar?

\medskip
\begin{wrapfigure}{r}{0.5\textwidth}
\vspace{-32pt}
\small
\begin{tableau}[1.75]{5}{4}{1.2}\label{tableauEx}
\C{/VC/}   \C{Ons} \C{*Cod}  \C{DepC} \C{DepV} \C{Max} 
\C{CV}      \C{ }	  \C{ }	 \C{*}   \C{ }   \C{*}
\C{CV}      \C{ }	  \C{ }	 \C{ }   \C{*}   \C{*}
\C{VC}      \C{*}	  \C{*}  \C{ }   \C{ }   \C{ }
\C{CV\D CV} \C{ }	  \C{ }	 \C{*}   \C{*}   \C{ }\end{tableau}
\vspace{-30pt} \setcounter{equation}{0}
\normalsize
\end{wrapfigure}
For example, in the CV-syllable model of Prince \& Smolensky (1993), what is learned 

\noindent from VC$\to$CV? Despite the ambiguity, it is clear that \Con{Ons} or \Con{*Cod} must outrank \Con{Max} (and less clearly, so must \Con{DepV} or \Con{DepC}). 


\bigskip\noindent
%----------------------------------------------------------------------------%
% Proposal
%----------------------------------------------------------------------------%
\textbf{Proposal}~~As this schematic example shows, even if the winner's precise character is unclear, the \emph{losers} may still present unambiguous contrasts. The relevant comparison is given in (\ref{def:hull}).
  

\begin{example}\label{def:hull}
% \textbf{Candidate-hull:} \\*     
The \emph{hull} of a candidate-set is the constraint-wise minima of the candidate's violations.
\end{example}

\noindent 
In essence, $hull(\{a,b\})$ projects the \emph{best} qualities of $a$ and $b$ onto an abstract candidate that violates only \Con{Max}, and this shared flaw is what allows inference in the face of ambiguity. This method factors ambiguity into candidate comparison and, as such, the candidate-hull can be used without modification in proposed learning algorithms for (stochastically) ranked or weighted constraints (for the latter, this is the linear-hull of weightings selecting $a$ and $b$).

% \bigskip\noindent

\bigskip\spacing{1.1}
\begin{wrapfigure}{r}{0.5\textwidth}
\vspace{-14pt}\small
\begin{tabular}{crr}
    \toprule
              & |\emph{Lex}|=62        & |\emph{Lex}|=254        \\
    \midrule    % 2529 strong languages, 2008 surface distinct
    |$Con$|   & $\mathcal{T}_s$: 2,140 & $\mathcal{T}_s$: 2,529  \\
        =10   & $\mathcal{T}_w$: 1,527 & $\mathcal{T}_w$: 2,008  \\
    \midrule    % 4723 strong languages, 3222 surface languages
                
    |$Con$|   & $\mathcal{T}_s$: 4,723 & $\mathcal{T}_s$: ???~~  \\
        =12   & $\mathcal{T}_w$: 3,222 & $\mathcal{T}_w$: ???~~  \\
    \bottomrule
\end{tabular}\normalsize
\vspace{-24pt} 
\normalsize
\end{wrapfigure}\spacing{1.2}
%----------------------------------------------------------------------------%
% Evaluation
%----------------------------------------------------------------------------%
\noindent\textbf{Evaluation}~~To test this method, we examined foot-based quantity-sensitive stress under the 10- and 12-constraint models of Tesar (2004) and Tesar \& Smolensky (2000) with their input-set of 62 strings of 2-5 light/heavy syllables plus 6 and 7 lights. We also generated typologies using all 254 strings of 2-7 light/heavy syllables (the last, unfinished). 

\medskip
In each case, the weak-generative typology $\mathcal{T}_w$ is much smaller than the strong $\mathcal{T}_s$ (the latter assigns different foot structures to homophonous languages). 
%For the 10-constraint/62-input model, our numbers replicate Tesar's exactly.
For most surface-languages, most ambiguous forms can be disambiguated by rankings gleaned from unambiguous forms in other tableaux (as Tesar notes), \emph{but} if the input set is incomplete, the omission of these forms renders much ambiguity irresolvable. In these cases, hulls provide crucial disambiguation. 

For example, /light-heavy-heavy/ yields 9 surface forms with 3 that are 2-ways ambiguous between footings. Despite the ambiguity, the hull of 
/\textsc{lhh}/$\to$[\textsc{\`lh\'h}] = \{[\textsc{(\`l)(h\'h)}], [\textsc{(\`lh)(\'h)}]\}) 
provides enough information to disambiguate candidates for /light-light-light/ (which also has 9 forms and 3 ambiguous pairs) so that   
/\textsc{lll}/$\to$[\textsc{\'ll\`l}] = \{[\textsc{(\'l)(l\`l)}], [\textsc{(\'ll)(\`l)}]\}) must be [\textsc{(\'l)(l\`l)}]. Resolving this ambiguity then, in turn, resolves the ambiguity in the first tableau. 
 

\bigskip\noindent
%----------------------------------------------------------------------------%
% Conclusions
%----------------------------------------------------------------------------%
\textbf{Conclusions}~~Our method allows a significant step away from supervised
learning that is broadly applicable to cases where learners have only partial
information about input-output mappings. In addition to dealing with noise, homophony, and hidden structure, hulls can extract common properties across multiple grammars (i.e., cophonologies) underlying variation. 

\end{document}
%----------------------------------------------------------------------------%
%----------------------------------------------------------------------------%
%----------------------------------------------------------------------------%
%----------------------------------------------------------------------------%

with tessmo 62 inputs: 2140 strong languages, 1527 surface languages
with all length<8 inputs: 2529 strong languages, 2008 surface languages

12 constraint model:
with tessmo 62 inputs: 4723 strong languages, 3222 surface languages
with all length<8 inputs: Generating (at 72%)


% input /lll/, the learner observes stress pattern [102]. At the surface, this is ambiguous between the two parses [[L]][lL] and [[Ll]][L], but the knowledge gleaned from the disjunctive hull for /lhh/ -> [201] allows the learner to rule out the latter parse; he thus knows that /lll/ maps to [[L]][lL]. With this knowledge in hand, the learner can return to the first ambiguous observation (/lhh/ -> [201], consistent with either [L][[hH]] or [Lh][[H]]) and fully resolve that ambiguity. Since /lll/ -> [[L]][lL], it must be the case /lhh/ maps to [L][[hH]] and not to [Lh][[H]]
